package 剑指II;

import 链表.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-08
 **/

public class Jz025链表中的两数相加 {

    /**
     * 给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。
     * 它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
     * 可以假设除了数字 0 之外，这两个数字都不会以零开头。
     * <p>
     * 示例1：
     * 输入：l1 = [7,2,4,3], l2 = [5,6,4]
     * 输出：[7,8,0,7]
     * 示例2：
     * 输入：l1 = [2,4,3], l2 = [5,6,4]
     * 输出：[8,0,7]
     * 示例3：
     * 输入：l1 = [0], l2 = [0]
     * 输出：[0]
     * <p>
     * 提示：
     * 链表的长度范围为 [1, 100]
     * 0 <= node.val <= 9
     * 输入数据保证链表代表的数字无前导 0
     * 进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。
     * <p>
     * 注意：本题与主站 445 题相同：https://leetcode-cn.com/problems/add-two-numbers-ii/
     */

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();

        while (l1 != null) {
            s1.append(l1.val);
            l1 = l1.next;
        }

        while (l2 != null) {
            s2.append(l2.val);
            l2 = l2.next;
        }

        List<Integer> result = new ArrayList<>();
        int lastCarry = 0;

        int lengthA = s1.length() - 1;
        int lengthB = s2.length() - 1;

        while (lengthA >= 0 && lengthB >= 0) {

            int numA = s1.charAt(lengthA) - '0';
            int numB = s2.charAt(lengthB) - '0';
            lengthA--;
            lengthB--;
            int num = numA + numB + lastCarry;
            result.add(num % 10);
            lastCarry = num / 10;

        }

        while (lengthA >= 0) {

            int numA = s1.charAt(lengthA) - '0';
            lengthA--;
            int num = numA + lastCarry;
            result.add(num % 10);
            lastCarry = num / 10;

        }

        while (lengthB >= 0) {

            int numB = s2.charAt(lengthB) - '0';
            lengthB--;
            int num = numB + lastCarry;
            result.add(num % 10);
            lastCarry = num / 10;

        }

        if (lastCarry != 0) {
            result.add(lastCarry);
        }

        ListNode head = new ListNode(-1);
        ListNode cur = head;

        for (int i = result.size() - 1; i >= 0; i--) {
            cur.next = new ListNode(result.get(i));
            cur = cur.next;
        }

        return head.next;
    }

}
